import com.sun.xml.internal.bind.v2.model.annotation.RuntimeAnnotationReader;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Author:王正浩
 * @Date 2022 07 30 16 59
 **/
public class study {


    private String haystack;

    /**
     * 最大公共前缀
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int length = strs.length;
        String str = strs[0];
        for (int i = 1; i < length; i++) {
            str = check(str, strs[i]);
            if (str.length() == 0) {
                break;
            }
        }
        return str;
    }

    public String check(String s1, String s2) {
        int result = Math.min(s1.length(), s2.length());
        int j = 0;
        while (j < result && s1.charAt(j) == s2.charAt(j)) {
            j++;
        }
        return s1.substring(0, j);
    }

    /**
     * 是否因为有效括号
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        int length = s.length() / 2;
        for (int i = 0; i < length; i++) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }

        return s.length() == 0;

    }

    public void Test() {
        Map<Character, Character> map = new HashMap<>();
        Deque<Character> stack = new LinkedList<>();

    }

    /**
     * 找一个数组中是否有相同的数,如果没有就放在该排序的位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int length = nums.length;
        int left = 0;
        int right = length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 最后一个单词的长度
     *
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        String[] strings = s.split(" ");
        return strings[strings.length - 1].length();
    }

    /**
     * 数组末尾+1;
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; j++) {
                    digits[j] = 0;
                }
                return digits;
            }

        }
        int[] ints = new int[n + 1];
        ints[0] = 1;
        return ints;
    }

    /**
     * 二进制求和
     *
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();

    }

    /**
     * 求x的算数平方根
     *
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;

    }

    /**
     * 删除有序链表中的相同数字
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null){
            return head;
        }
        ListNode listNode=head;
        while (listNode.next!=null){
            if (listNode.val==listNode.next.val){
                listNode.next=listNode.next.next;
            }else {
            listNode=listNode.next;

            }

        }
        return head;

    }

    /**
     * 二叉树的中序遍历
     * @param root
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> stk=new LinkedList<>();
        while (root!=null||!stk.isEmpty()){
            while (root!=null){
                stk.push(root);
                root=root.left;
            }
            root=stk.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }

    /**
     *
     * @param nums
     * @return
     */
    public  TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

    /**
     * 杨辉三角
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list=new ArrayList<>();
        if (numRows==0){
            return null;
        }
        for (int i = 0; i < numRows; i++) {
            List<Integer> row=new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j==0||j==i){
                    row.add(1);
                }else {
                    row.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
                }
            }
            list.add(row);
        }
        return list;

    }
    /**
     * 杨辉三角2
     * @param rowIndex
     * @return
     */
    public  static List<Integer> getRow(int rowIndex) {
        List<List<Integer>> list=new ArrayList<>();

        for (int i = 0; i <= rowIndex; i++) {
            List<Integer> ret=new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j==0||j==i){
                    ret.add(1);
                }else {
                    ret.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
                }
            }
            list.add(ret);
        }
        return list.get(rowIndex);
    }

    /**
     * 买股票最佳时间
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }

    /**
     * 找出只出现一次的数字
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        int sing=0;
        for (int num : nums) {
            sing^=num;
        }
        return sing;

    }

    /**
     * 多数元素
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    /**
     * 判断回文串
     * @param s
     * @return
     */
    public static boolean isPalindrome(String s) {
        StringBuffer sgood = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }
        int n = sgood.length();
        int left = 0, right = n - 1;
        while (left < right) {
            if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }

    /**
     * 求excel表名称
     * @param columnNumber
     * @return
     */
    public static String convertToTitle(int columnNumber) {
        StringBuffer sb = new StringBuffer();
        while (columnNumber > 0) {
            int a0 = (columnNumber - 1) % 26 + 1;
            sb.append((char)(a0 - 1 + 'A'));
            columnNumber = (columnNumber - a0) / 26;
        }
        return sb.reverse().toString();
    }

    /**
     * 存在重复元素
     * @param nums
     * @return
     */
    public static boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 存在重复元素II
     * @param nums
     * @param k
     * @returnProject
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num=nums[i];
            if (map.containsKey(num)&&i-map.get(num)<=k){
                return true;
            }
            map.put(num,i);
        }
            return false;
    }

    /**
     * 汇总区间
     * @param nums
     * @return
     */
    public static List<String> summaryRanges(int[] nums) {
        List<String> list=new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            StringBuilder stringBuilder=new StringBuilder();
            int temp=i;
            while (i<nums.length-1&&nums[i]+1==nums[i+1]){
                i++;
            }
            if (i==temp){
                stringBuilder.append(nums[i]);
            }else {
                stringBuilder.append(nums[temp]);
                stringBuilder.append("->");
                stringBuilder.append(nums[i]);
            }
            list.add(stringBuilder.toString());
        }

        return list;
    }

    /**
     * 找出没出现的数字
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n;
    }

    /**
     * 移动零
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        if (nums==null){
            return;
        }
        int j=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!=0){
                nums[j]=nums[i];
                j++;
            }
        }
        for (int i = j; i < nums.length; i++) {
            nums[i]=0;
        }
    }

    /**
     * 非递增序列的最小子序列
     * @param nums
     * @return
     */
    public static List<Integer> minSubsequence(int[] nums) {
        List<Integer> list=new ArrayList<>();
        Arrays.sort(nums);
        int sum=0;
        int flag=-1;
         sum = Arrays.stream(nums).sum();
         int s=0;
        for (int i = nums.length-1; i >=0; i--) {
            s+=nums[i];
            list.add(nums[i]);
            if (s*2>sum){
                break;
            }
        }
        return list;
    }

    /**
     * 找两个数组的公共元素
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list=new ArrayList();
        for (int i = 0; i < nums1.length; i++) {
            int x=nums1[i];
            for (int j = 0; j < nums2.length; j++) {
                if (x==nums2[j]&&!list.contains(x)){
                    list.add(x);
                    break;
                }
            }
        }
        Integer[] integers = list.toArray(new Integer[0]);
        int[] ints = Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();
        return ints;
    }

    /**
     * 第三大的数
     * @param nums
     * @return
     */
    public static int thirdMax(int[] nums) {

        Arrays.sort(nums);
        List<Integer> list=new ArrayList<>();
        for (int num : nums) {
            if (!list.contains(num)){
                list.add(num);
            }
        }
        if (list.size()==1){
            return list.get(0);
        }else if (list.size()==2){
            return list.get(1);
        }else {
            return list.get(list.size()-3);
        }
    }

    /**
     * 在二叉树中增加一行
     * @param root
     * @param val
     * @param depth
     * @return
     */
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode ans = new TreeNode(val);
            ans.left = root;
            return ans;
        }
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        int cur = 1;
        while (!d.isEmpty()) {
            int sz = d.size();
            while (sz-- > 0) {
                TreeNode t = d.pollFirst();
                if (cur == depth - 1) {
                    TreeNode a = new TreeNode(val), b = new TreeNode(val);
                    a.left = t.left; b.right = t.right;
                    t.left = a; t.right = b;
                } else {
                    if (t.left != null) d.addLast(t.left);
                    if (t.right != null) d.addLast(t.right);
                }
            }
            cur++;
        }
        return root;
    }

    /**
     * 数组中字符串匹配
     * @param words
     * @return
     */
    public List<String> stringMatching(String[] words) {
        List<String> list=new LinkedList<>();
        for (String word : words) {
            for (int i = 0; i < words.length; i++) {
                if (word.length()>=words[i].length()){
                    continue;
                }
                if (words[i].contains(word)){
                    list.add(word);
                    break;
                }
            }
        }
        return list;
    }

    /**
     * 找到数组中消失的数字
     * @param nums
     * @return
     */
    public  static List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i <nums.length; i++) {
            set.add(nums[i]);
        }
        for (int i = 1; i <= nums.length; i++) {
            if(set.add(i)){
                res.add(i);
            }
        }
        return res;
//        int n = nums.length;
//        for (int num : nums) {
//            int x = (num - 1) % n;
//            nums[x] += n;
//        }
//        List<Integer> ret = new ArrayList<Integer>();
//        for (int i = 0; i < n; i++) {
//            if (nums[i] <= n) {
//                ret.add(i + 1);
//            }
//        }
//        return ret;
    }

    /**
     * 分发饼干
     * @param g
     * @param s
     * @return
     */
    public  static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        List<Integer> list = Arrays.stream(s).boxed().collect(Collectors.toList());
        int res=0;
        for (int i = 0; i < g.length; i++) {
            int now=g[i];
                for (Integer f : list) {
                if (now<=f){
                    res++;
                    list.remove(f);
                    break;
                }
            }
        }
        return res;
    }

    /**
     * 岛屿周长问题
     * @param grid
     * @return
     */
    public int islandPerimeter(int[][] grid) {
        //重点关注前面遍历过得方格，如果之前有相邻方格，就-2;
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rsp = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    rsp += 4;
                    if (i > 0 && grid[i - 1][j] == 1) {
                        rsp -= 2;
                    }
                    if (j > 0 && grid[i][j - 1] == 1) {
                        rsp -= 2;
                    }
                }
            }
        }
        return rsp;
    }

    /**
     * 最大连续"1"的个数
     * @param nums
     * @return
     */
    public static int findMaxConsecutiveOnes(int[] nums) {
        int res=0;
        List<Integer> list=new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==1){
                res++;
            }else{
                list.add(res);
                res=0;
            }
        }
        list.add(res);
        int[] array = list.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(array);
        return array[array.length-1];
    }
    public static int findPoisonedDuration(int[] timeSeries, int duration) {
        int ans = 0;
        int expired = 0;
        for (int i = 0; i < timeSeries.length; ++i) {
            if (timeSeries[i] >= expired) {
                ans += duration;
            } else {
                ans += timeSeries[i] + duration - expired;
            }
            expired = timeSeries[i] + duration;
        }
        return ans;
    }

    /**
     * 分糖果
     * @param candyType
     * @return
     */
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<Integer>();
        for (int candy : candyType) {
            set.add(candy);
        }
        return Math.min(set.size(), candyType.length / 2);
    }

    /**
     * 环形链表
     * @param head
     * @return
     */
    public  static boolean hasCycle(ListNode head) {
        Set<ListNode> set=new HashSet<>();
        while (head!=null){
            if (!set.add(head)){
                return true;
            }
            head=head.next;
        }
        return false;
    }

    /**
     * 相交链表
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set set=new HashSet();
        while (headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while (headB!=null){
            if (!set.add(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return null;

    }

    /**
     * 颠倒二进制位
     * @param n
     * @return
     */
    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            rev |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return rev;

    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode curr=head;
        while (curr!=null){
            ListNode next = curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }

    /**
     * 反转字符串中的元音字母
     * @param s
     * @return
     */
    public String reverseVowels(String s) {
        int n=s.length();
        char[] array = s.toCharArray();
        int j=n-1;
        int i=0;
        while (i<j){
            while (i<n&&"aeiouAEIOU".indexOf(array[i])<0){
                ++i;
            }
            while (j > 0&&"aeiouAEIOU".indexOf(array[j])<0){
                --j;
            }
            if (i<j){
                char temp=array[i];
                array[i]=array[j];
                array[j]=temp;
                ++i;
                --j;
            }
        }
        return new String(array);
    }
//
    public static void main(String[] args) {
//        findPoisonedDuration(new int[]{
//            1,2
//        },2);
//        findContentChildren(new int[]{
//                1,2,3
//        },new int[]{
//                3
//        });
//        findMaxConsecutiveOnes(new int[]{
//                1,1,0,1,1,1
//        });
//    findDisappearedNumbers(new int[]{
//            1,1
//    });
//            intersection(new int[]{
//                    1,2,2,1
//            },new int[]{2,2});
//        moveZeroes(new int[]{
//                1,3,12,0,0,9
//        });
//        System.out.println(
//                missingNumber(new int[]{
//                0,1
//        }));
//        System.out.println(summaryRanges(new int[]{
//                0, 2, 3, 4, 6, 8
//        }));
//        System.out.println(
//                containsNearbyDuplicate(new int[]{1, 2, 3, 1,2,3}, 3));

//            addBinary("11011","11001");
  //      System.out.println("mySqrt = " + mySqrt(1100000));
//        System.out.println(getRow(3).toString());
//        System.out.println("maxProfit(new int[]{\n                7,6,4,3,5,4,2,1,9\n        }) = "
//                + maxProfit(new int[]{7,1, 5,3,6,4
//        }));
//        System.out.println(
//                singleNumber(new int[]{
//                2,2,1
//        }));
//        System.out.println(
//                majorityElement(new int[]{
//                3,2,3
//        }));
//        System.out.println(
//                isPalindrome("A man, a plan, a canal: Panama"));
//        System.out.println(
//                convertToTitle(701));
//        System.out.println(
//                containsDuplicate(new int[]{
//                1,5,-2,-4,0
//        }));
//        int[] ints = {1, 3, 5, 7};
//        int i = Arrays.binarySearch(ints, 5);
//        System.out.println(i);
    }

}


